package lab2.datastructures;

import lab2.testSortCol.CollectionWithGet;

/**
 * An implementaion of a sorted linked collection, 
 * which is an extension of linked list.
 * The elements are ordered ascending according to their
 * comparable rules set and may be duplicates. 
 * 
 * @author Anders & Joanna
 *
 * @param <E> needs to implement comparable interface
 */
public class SLCwithGet <E extends Comparable<? super E>>
	   extends LinkedCollection<E>
	   implements CollectionWithGet<E>{
	
	/**
     * Adds an element to the collection and order them ascending
     * according to their Comparable rule set.
     * The iterator gives the first element in the list which is
     * the smallest in order.      
     * 
     * @param element the object to add into the list
     * @return true if the object has been added to the list.
     * @throws NullPointerException if parameter <tt>element<tt> is null. 
     */
	@Override									
    public boolean add(E element ) {
		if (element == null ){
        	  throw new NullPointerException();
        }
        else {
           // Case 1: List is empty
        	//Case 2: Element is less than the key of the first node
           if(head == null || (element.compareTo(head.element) < 0)){
        	   Entry firstEntry = new Entry(element,null);
    		   firstEntry.next = head;
    		   head = firstEntry;
           }
           //Case 3: Element is larger than the first key
           else{
        	    insert(element);
           }
           return true;
	    }
    } // add
	
	private void insert(E element) {		
		Entry current = head;
		
		while(current.next != null && element.compareTo(current.next.element) > 0){ 
				current = current.next;	
		}
		
		//Bigger node found - insert after current 
		Entry newNode = new Entry(element,null);
		newNode.next = current.next;
		current.next = newNode;
	}

	private E find(E element){
		Entry current = head;
	
		while(element.compareTo(current.element) > 0){
			current = current.next;
			if(current == null){
				return null;
			}
			
		}
		if(element.compareTo(current.element) == 0){
			return current.element;
		}
		else{
			return null;
		}
	}
	
	@Override
	public E get(E e) {
		if(head == null){
			return null;
		}
		else{
			return find(e);
		}
	}
}
